home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / comm / mail / Mutt089src.lha / Mutt-0.89i-AMIGA / src / rx / rxbitset.c < prev    next >
C/C++ Source or Header  |  1998-01-28  |  7KB  |  365 lines
  1. /*    Copyright (C) 1995, 1996 Tom Lord
  2.  * 
  3.  * This program is free software; you can redistribute it and/or modify
  4.  * it under the terms of the GNU Library General Public License as published by
  5.  * the Free Software Foundation; either version 2, or (at your option)
  6.  * any later version.
  7.  * 
  8.  * This program is distributed in the hope that it will be useful,
  9.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.  * GNU Library General Public License for more details.
  12.  * 
  13.  * You should have received a copy of the GNU Library General Public License
  14.  * along with this software; see the file COPYING.  If not, write to
  15.  * the Free Software Foundation, 59 Temple Place - Suite 330, 
  16.  * Boston, MA 02111-1307, USA. 
  17.  */
  18.  
  19.  
  20. /*
  21.  * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
  22.  */
  23.  
  24.  
  25. #include "rxall.h"
  26. #include "rxbitset.h"
  27.  
  28.  
  29. #ifdef __STDC__
  30. int
  31. rx_bitset_is_equal (int size, rx_Bitset a, rx_Bitset b)
  32. #else
  33. int
  34. rx_bitset_is_equal (size, a, b)
  35.      int size;
  36.      rx_Bitset a;
  37.      rx_Bitset b;
  38. #endif
  39. {
  40.   int x;
  41.   RX_subset s;
  42.  
  43.   if (size == 0)
  44.     return 1;
  45.  
  46.   s = b[0];
  47.   b[0] = ~a[0];
  48.  
  49.   for (x = rx_bitset_numb_subsets(size) - 1; a[x] == b[x]; --x)
  50.     ;
  51.  
  52.   b[0] = s;
  53.   return !x && (s == a[0]);
  54. }
  55.  
  56.  
  57. #ifdef __STDC__
  58. int
  59. rx_bitset_is_subset (int size, rx_Bitset a, rx_Bitset b)
  60. #else
  61. int
  62. rx_bitset_is_subset (size, a, b)
  63.      int size;
  64.      rx_Bitset a;
  65.      rx_Bitset b;
  66. #endif
  67. {
  68.   int x;
  69.   x = rx_bitset_numb_subsets(size) - 1;
  70.   while (x-- && ((a[x] & b[x]) == a[x]));
  71.   return x == -1;
  72. }
  73.  
  74.  
  75. #ifdef __STDC__
  76. int
  77. rx_bitset_empty (int size, rx_Bitset set)
  78. #else
  79. int
  80. rx_bitset_empty (size, set)
  81.      int size;
  82.      rx_Bitset set;
  83. #endif
  84. {
  85.   int x;
  86.   RX_subset s;
  87.   s = set[0];
  88.   set[0] = 1;
  89.   for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x)
  90.     ;
  91.   set[0] = s;
  92.   return !s;
  93. }
  94.  
  95. #ifdef __STDC__
  96. void
  97. rx_bitset_null (int size, rx_Bitset b)
  98. #else
  99. void
  100. rx_bitset_null (size, b)
  101.      int size;
  102.      rx_Bitset b;
  103. #endif
  104. {
  105.   rx_bzero ((char *)b, rx_sizeof_bitset(size));
  106. }
  107.  
  108.  
  109. #ifdef __STDC__
  110. void
  111. rx_bitset_universe (int size, rx_Bitset b)
  112. #else
  113. void
  114. rx_bitset_universe (size, b)
  115.      int size;
  116.      rx_Bitset b;
  117. #endif
  118. {
  119.   int x = rx_bitset_numb_subsets (size);
  120.   while (x--)
  121.     *b++ = ~(RX_subset)0;
  122. }
  123.  
  124.  
  125. #ifdef __STDC__
  126. void
  127. rx_bitset_complement (int size, rx_Bitset b)
  128. #else
  129. void
  130. rx_bitset_complement (size, b)
  131.      int size;
  132.      rx_Bitset b;
  133. #endif
  134. {
  135.   int x = rx_bitset_numb_subsets (size);
  136.   while (x--)
  137.     {
  138.       *b = ~*b;
  139.       ++b;
  140.     }
  141. }
  142.  
  143.  
  144. #ifdef __STDC__
  145. void
  146. rx_bitset_assign (int size, rx_Bitset a, rx_Bitset b)
  147. #else
  148. void
  149. rx_bitset_assign (size, a, b)
  150.      int size;
  151.      rx_Bitset a;
  152.      rx_Bitset b;
  153. #endif
  154. {
  155.   int x;
  156.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  157.     a[x] = b[x];
  158. }
  159.  
  160.  
  161. #ifdef __STDC__
  162. void
  163. rx_bitset_union (int size, rx_Bitset a, rx_Bitset b)
  164. #else
  165. void
  166. rx_bitset_union (size, a, b)
  167.      int size;
  168.      rx_Bitset a;
  169.      rx_Bitset b;
  170. #endif
  171. {
  172.   int x;
  173.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  174.     a[x] |= b[x];
  175. }
  176.  
  177.  
  178. #ifdef __STDC__
  179. void
  180. rx_bitset_intersection (int size,
  181.             rx_Bitset a, rx_Bitset b)
  182. #else
  183. void
  184. rx_bitset_intersection (size, a, b)
  185.      int size;
  186.      rx_Bitset a;
  187.      rx_Bitset b;
  188. #endif
  189. {
  190.   int x;
  191.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  192.     a[x] &= b[x];
  193. }
  194.  
  195.  
  196. #ifdef __STDC__
  197. void
  198. rx_bitset_difference (int size, rx_Bitset a, rx_Bitset b)
  199. #else
  200. void
  201. rx_bitset_difference (size, a, b)
  202.      int size;
  203.      rx_Bitset a;
  204.      rx_Bitset b;
  205. #endif
  206. {
  207.   int x;
  208.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  209.     a[x] &=  ~ b[x];
  210. }
  211.  
  212.  
  213. #ifdef __STDC__
  214. void
  215. rx_bitset_revdifference (int size,
  216.              rx_Bitset a, rx_Bitset b)
  217. #else
  218. void
  219. rx_bitset_revdifference (size, a, b)
  220.      int size;
  221.      rx_Bitset a;
  222.      rx_Bitset b;
  223. #endif
  224. {
  225.   int x;
  226.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  227.     a[x] = ~a[x] & b[x];
  228. }
  229.  
  230. #ifdef __STDC__
  231. void
  232. rx_bitset_xor (int size, rx_Bitset a, rx_Bitset b)
  233. #else
  234. void
  235. rx_bitset_xor (size, a, b)
  236.      int size;
  237.      rx_Bitset a;
  238.      rx_Bitset b;
  239. #endif
  240. {
  241.   int x;
  242.   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
  243.     a[x] ^= b[x];
  244. }
  245.  
  246.  
  247. #ifdef __STDC__
  248. unsigned long
  249. rx_bitset_hash (int size, rx_Bitset b)
  250. #else
  251. unsigned long
  252. rx_bitset_hash (size, b)
  253.      int size;
  254.      rx_Bitset b;
  255. #endif
  256. {
  257.   int x;
  258.   unsigned long answer;
  259.  
  260.   answer = 0;
  261.  
  262.   for (x = 0; x < size; ++x)
  263.     {
  264.       if (RX_bitset_member (b, x))
  265.     answer += (answer << 3) + x;
  266.     }
  267.   return answer;
  268. }
  269.  
  270.  
  271. RX_subset rx_subset_singletons [RX_subset_bits] = 
  272. {
  273.   0x1,
  274.   0x2,
  275.   0x4,
  276.   0x8,
  277.   0x10,
  278.   0x20,
  279.   0x40,
  280.   0x80,
  281.   0x100,
  282.   0x200,
  283.   0x400,
  284.   0x800,
  285.   0x1000,
  286.   0x2000,
  287.   0x4000,
  288.   0x8000,
  289.   0x10000,
  290.   0x20000,
  291.   0x40000,
  292.   0x80000,
  293.   0x100000,
  294.   0x200000,
  295.   0x400000,
  296.   0x800000,
  297.   0x1000000,
  298.   0x2000000,
  299.   0x4000000,
  300.   0x8000000,
  301.   0x10000000,
  302.   0x20000000,
  303.   0x40000000,
  304.   0x80000000
  305. };
  306.  
  307.  
  308. /* 
  309.  * (define l (let loop ((x 0) (l '())) (if (eq? x 256) l (loop (+ x 1) (cons x l)))))
  310.  * (define lb (map (lambda (n) (number->string n 2)) l))
  311.  * (define lc (map string->list lb))
  312.  * (define ln (map (lambda (l) (map (lambda (c) (if (eq? c #\1) 1 0)) l)) lc))
  313.  * (define lt (map (lambda (l) (apply + l)) ln))
  314.  */
  315.  
  316. static int char_pops[256] = 
  317. {
  318.   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  319.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  320.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  321.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  322.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  323.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  324.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  325.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  326.   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  327.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  328.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  329.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  330.   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  331.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  332.   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  333.   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
  334. };
  335.  
  336. #define RX_char_population(C) (char_pops[C])
  337.  
  338. #ifdef __STDC__
  339. int
  340. rx_bitset_population (int size, rx_Bitset a)
  341. #else
  342. int
  343. rx_bitset_population (size, a)
  344.      int size;
  345.      rx_Bitset a;
  346. #endif
  347. {
  348.   int x;
  349.   int total;
  350.   unsigned char s;
  351.  
  352.   if (size == 0)
  353.     return 0;
  354.  
  355.   total = 0;
  356.   x = sizeof (RX_subset) * rx_bitset_numb_subsets(size) - 1;
  357.   while (x >= 0)
  358.     {
  359.       s = ((unsigned char *)a)[x];
  360.       --x;
  361.       total = total + RX_char_population (s);
  362.     }
  363.   return total;
  364. }     
  365.